import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.Stack;

public class code3 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if(root == null) {
            return list;
        }

        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;
        TreeNode pre = root;

        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            //右子树为空||已经打印过了
            if(top.right == null || top.right == pre) {
                list.add(top.val);
                stack.pop();
                pre = top;
            } else  {
                cur = top.right;
            }
        }
        return list;
    }

}